package 动态规划.dp声明正序And倒序.射箭比赛这道题的思维发散;

public class 射箭比赛中的最大得分复习 {
	public static void main(String []args) {
//		boolean flag = true;
//		System.out.println(flag);
//		int i = 0;
//		for(;i <10 && flag ;i++ ) {
//			if(i == 5) {
//				flag = false;
//			}
//			System.out.println(i);
//		}
//		System.out.println(i);
//		int arrows = 9;
//		int arrows = 3;
//		int arr[] = {1,1,0,1,0,0,2,1,0,1,2,0};
		int arrows = 100000;
		int arr[] = {0,0,0,0,0,0,0,0,0,0,0,100000};
		long t1 = System.currentTimeMillis();
		System.out.println(process(arrows,arr,1));
		long t2 = System.currentTimeMillis();
		System.out.println(t2 - t1);
		System.out.println(a);
		System.out.println(soluton(arrows,arr));
//		System.out.println();
		System.out.println(dp(arrows,arr));
		System.out.println("*****************");
		System.out.println(dpClear(arrows,arr));
		System.out.println("*****************");
		System.out.println(dpFinal(arrows,arr));
	}
	//*************************************************************************************
	
	// 有问题 下面的 逻辑
	
	/**
	 * 递归  形成 二叉树 的模型 
	 * 这可以说是一个 模板了
	 * 下面  这种选或者 不选的  产生 的  就是二叉树
	 * 1.选 或者 不 选
	 *  有一个选择的 数组 choice []
	 *  选择的范围 就是 choice [] 里面的 内容
	 * 2. 可重复选 或者 不可重复选(01 背包 和 完全背包的区别)
	 *  两者的区别 就在于 是否
	 * 对上面做个  code 演示
	 */
	public static void function(int rest,int index,int choice[]) {
		//basecase
		if(rest ==0 )
			return ;
		
		// 选 (不可重复选)
		function(rest - choice[index],index + 1,choice);
		// 如果可重复选的话 
		//function(rest - choice[index],index,choice);
		
		// 不选 (不可重复选)
		function(rest,index + 1,choice);
		
		
		
		// 如果 可重复选  
		// 但是下面的 code 死循环了
//		function(rest,index,choice);
	
		// 这样就不会死循环了  (虽然可以重复选 但是 不选择当前的 index 选择 那肯定跳到下一层啊 这没有什么毛病)
	//	function(rest,index + 1,choice);
		
	}
	
	//**********************************************************************************
	
	
// 返回比赛的 最大得分 靶子 的 得分 为  0 ~  11 其实 就是数组的下标 
	/**
	 * 
	 * @param arrows  当前 箭的个数
	 * @param arr  int [12] 0 ~ 11 代表靶子 
	 * @param index  当前 在 那个 靶子 做 判断
	 * @return  最大 得分
	 */
	static int a;
	public static int process(int arrows,int arr[],int index) {
		a++;  
		//basecase
		if(arrows == 0) {
			return 0;
		}
		//  这种情况 可以 直接避免 || arrows < 0  x小于 零 的情况 可以直接 在 for 循环中 给 解决掉
		if(index == 12 ) {
			return 0;
		}
		/**
		 * if(arrows == 0  || index == 12){
		 * 		return 0;
		 * }
		 * 将上面的 代码 合并成 一个 语句 注意 顺序 
		 * arrows 必须在   前面   arrows 才是 核心 的   basecase
		 */
		int ans  = 0;
		/**
		  *  这直接 就不用写   不写的 话 直接 可以 剪掉 好多 分支
		 * ans = Math.max(ans, process(arrows,arr,i + 1));
		 * 这句 代码 的 影响的 速度 是   很大 的 
		 * 其实 画个 图 就明白 好多了 为啥 可以 直接 不写 
		 * 重复的 过程 可以 直接 剪掉分支 这也是  一种思想
		 */
		for(int  i = index ;i < arr.length; i++) {
//			ans = Math.max(ans, process(arrows,arr,i + 1));
//			ans = process(arrows, arr,i + 1);  这样写 是错的  
			if(arrows >= arr[i] + 1) {
				ans = Math.max(ans , process(arrows - arr[i] -1,arr,i + 1) + i);
			}
		}
		return ans;
	}
	/**
	 * 采用 记忆化 搜索的 方法 来解决 
	 * @param arrows
	 * @param arr
	 */
	public static int soluton(int arrows,int arr[]) {
		int len = arr.length;
		int dp [][] = new int[arrows + 1][len + 1];
//		for(int i = 1 ;i <= arrows ;i++) {
//			for(int j = 0 ;j < len ;j++) {
//				dp[i][j] = -1;
//			}
//		}
		for(int i = 0 ;i <= arrows ;i++) {
			for(int j = 0 ;j <= len ;j++) {
				dp[i][j] = -1;
			}
		}
	  MemorySearch(arrows,arr,0,dp);
		return dp[arrows][0];
	}
	public static int MemorySearch(int arrows,int arr[],int index,int dp[][]) {
		if(dp[arrows][index] != -1) {
			return dp[arrows][index];
		}
		if(arrows == 0 || index ==12) {
//			dp[arrows][index] = 0;
//			return 0;
			return dp[arrows][index] = 0;
		}
		int ans = 0;
		for(int  i = index ;i < arr.length; i++) {
			if(arrows >= arr[i] + 1) {
				ans = Math.max(ans, MemorySearch(arrows - arr[i] - 1,arr,i + 1,dp) + i);
			}
		}
		return dp[arrows][index] = ans;
	}
	public static int dp(int arrows,int arr[]) {
		int len = arr.length;
		int dp [][] = new int [arrows + 1][len + 1];
		for(int i = 1;i <= arrows ;i++) {
			for(int j = len - 1;j >= 0; j-- ) {
				int ans  = 0;
				for(int k = j ;k < len ;k++) {
					if(i >= arr[k] + 1) {
						ans = Math.max(ans, dp[i - arr[k] - 1][k + 1] + k);
					}
				}
				dp[i][j] = ans; 
			}
		}
		return dp[arrows][0];
	}
	public static int dpClear(int arrows,int arr[]) {
		int len = arr.length;
		int dp [][] = new int [len + 1][arrows + 1];
		for(int arrow = 1 ;arrow <= arrows ;arrow++) {
			for(int index = len - 1 ;index >= 0; index--) {
				int ans = 0;
				for(int i = index ;i < len ;i++) {
					if(arrow >= arr[i] + 1) {
						ans = Math.max(ans,dp[i + 1][arrow - arr[i] -1] + i);
					}
				}
				dp[index][arrow] = ans;
			}
		}
		return dp[0][arrows];
	}
	public static int dpFinal(int arrows,int arr[]) {
		int len = arr.length;
		int dp [][]  = new int [len + 1][arrows + 1];
		for(int arrow = 1;arrow <= arrows ; arrow++) {
			for(int index = len - 1;index >= 0;index--) {
				dp[index][arrow] = dp[index + 1][arrow];
				if(arrow > arr[index] + 1) {
					dp[index][arrow] = Math.max(dp[index + 1][arrows - arr[index] - 1] + index,dp[index][arrow]);
				}
			}
		}
		return dp[0][arrows];
	}
}
